package _20_十大排序算法;

import java.util.Arrays;

/**
 * 如果两个元素相同，并且排序后，相对顺序保持不变，那么此排序算法就是稳定的排序算法
 *
 * 原地排序，不依赖于外界的资源，或使用少数资源
 */
public class _01_冒泡排序 {

    public static void main(String[] args) {
        _01_冒泡排序 v = new _01_冒泡排序();

        int[] ins = new int[]{2, 3, 1, 5, 4, 2};
        v.bubbleSort2(ins);

        System.out.println(Arrays.toString(ins));
    }

    // 冒泡排序，比较相邻元素，如果谁大就和谁交换位置，如果比较一轮，那么那个最大的元素就在最后
    // 稳定的排序算法
    public void bubbleSort(int[] nums) {
        int len = nums.length;
        for (int i = len; i > 1; i--) {
            for (int j = 1; j < i; j++) {
                if (nums[j] < nums[j - 1]) swap(nums, j, j - 1);
            }
        }
    }

    // 冒泡排序优化1，如果数组元素已经是排序的，那么就无须在从重复排序
    public void bubbleSort1(int[] nums) {
        int len = nums.length;
        for (int i = len; i > 1; i--) {
            boolean isSort = true;
            for (int j = 1; j < i; j++) {
                if (nums[j] < nums[j - 1]) {
                    swap(nums, j, j - 1);
                    isSort = false;
                }
            }
            if (isSort) return;
        }
    }

    // 如果排序后，后面已经部分排序，所以后面部分就不需要排序
    public void bubbleSort2(int[] nums) {
        int len = nums.length;
        for (int i = len - 1; i > 0; i--) {
            int sortIndex = i;
            for (int j = 1; j <= i; j++) {
                if (nums[j] < nums[j - 1]) {
                    swap(nums, j, j - 1);
                    sortIndex = j;
                }
            }
            i = sortIndex;
        }
    }

    public void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
